package com.base.bitoperation;

/**
 * 318. 最大单词长度乘积
 *
 * @author leon
 * @date 2021年11月17日 21:52
 */
public class MaxProduct {
    public int maxProduct(String[] words) {
        int n = words.length;
        int[][] hash = new int[n][26];
        for(int i=0;i<n;i++){
            for(int j = 0;j<words[i].length();j++){
                int index = words[i].charAt(j)-'a';
                if(hash[i][index]==0){
                    hash[i][index] = 1;
                }
            }
        }
        int max = 0;
        // 时间复杂度为26^n^2;
        for(int i = 0;i<n;i++){
            int iLength = words[i].length();
            for(int j = i+1;j<n;j++){
                if(andWord(hash[i],hash[j])){
                    int tmp = iLength*words[j].length();
                    max = tmp>max?tmp:max;
                }
            }
        }
        return max;
    }

    private boolean andWord(int[] a,int[] b){
        for(int i = 0;i<26;i++){
            if(a[i]+b[i]==2){
                return false;
            }
        }
        return true;
    }

//    作者：LeetCode-Solution
//    链接：https://leetcode-cn.com/problems/maximum-product-of-word-lengths/solution/zui-da-dan-ci-chang-du-cheng-ji-by-leetc-lym9/
//    来源：力扣（LeetCode）
//    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
    public int maxProduct1(String[] words) {
        int length = words.length;
        int[] masks = new int[length];
        for (int i = 0; i < length; i++) {
            String word = words[i];
            int wordLength = word.length();
            for (int j = 0; j < wordLength; j++) {
                // << 运算
                // 原数a << 位数n       ---- 一个数a左移n位
                // eg: 1 << 3 ==>  001 变为 100   :也就是3变成6
                // 所有这里: 如果存在abd字符串,那么对应二进程我们应该为1011
                // 1>>0 | 1>>1| 1>>3 ==> 1|2|6 ==> 0001|0010|1000=1011
                System.out.println(word.charAt(j) - 'a');
                System.out.println(1 << (word.charAt(j) - 'a'));
                System.out.println(masks[i]|(1 << (word.charAt(j) - 'a')));

                masks[i] |= 1 << (word.charAt(j) - 'a');
            }
        }
        int maxProd = 0;
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                if ((masks[i] & masks[j]) == 0) {
                    maxProd = Math.max(maxProd, words[i].length() * words[j].length());
                }
            }
        }
        return maxProd;
    }



    public static void main(String[] args) {
        String[] test = {"abcw","baz","foo","bar","xtfn","abcdef"};
        new MaxProduct().maxProduct1(test);
    }
}
